﻿
#pragma once
#include<iostream>
#include<string>
#include<queue>
#include<stack>
using namespace std;

struct TreeNode {
	int val;
    TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
	
};


string treestr(TreeNode* root)
	{
		string str;
		if (root == nullptr)
		{
			return str;
		}
		if (root->left || root->right)
		{
			str += '(';
			str += treestr(root->left);
			str += ')';
		}
		if (root->left || root->right)
		{
			str += '(';
			str += treestr(root->left);
			str += ')';
		}
		return str;
	}


vector<vector<int>>  treesequence(TreeNode* root)
{
	vector<vector<int>> vv;
	
	int levesize = 0;
	queue<TreeNode*> q;
	if (root)
	{
		levesize = 1;
		q.push(root);
	}
	while (!q.empty())
	{
		
		vector<int> v;
		while (levesize--)
		{
			TreeNode* front = q.front();
			if (front->left) q.push(front->left);
			if (front->right) q.push(front->right);
			v.push_back(front->val);
			q.pop();
		}
		vv.push_back(v);
		levesize = q.size();
	}
	reverse(vv.begin(), vv.end());
	return vv;

}

bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{
	if (root == nullptr)
		return false;

	// 前序遍历的思路，找x结点的路径
 // 遇到root结点先push⼊栈，因为root就算不是x，但是root可能是根->x路径中⼀
		path.push(root);
	if (root == x)
		return true;
	if (GetPath(root->left, x, path))
		return true;
	if (GetPath(root->right, x, path))
		return true;

	// 如果左右⼦树都没有x，那么说明上⾯⼊栈的root不是根->x路径中⼀个分⽀结点
	// 所以要pop出栈，回退，继续去其他分⽀路径进⾏查找
	path.pop();

	return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	stack<TreeNode*> pPath, qPath;
	GetPath(root, p, pPath);
	GetPath(root, q, qPath);
	// 模拟链表相交，两个路径找交点
	// ⻓的先⾛差距步，再⼀起⾛找交点
	while (pPath.size() != qPath.size())
	{
		if (pPath.size() > qPath.size())
			pPath.pop();
		else
			qPath.pop();
	}
	while (pPath.top() != qPath.top())
	{
		pPath.pop();
		qPath.pop();
	}
	return pPath.top();
}
